package question.solution46;

import question.SolutionTemplate;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution46 implements SolutionTemplate {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> arrange = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            arrange = getNewArrange(arrange, nums[i]);
        }
        return arrange;

    }

    private List<List<Integer>> getNewArrange(List<List<Integer>> oldArrange, int num){
        List<List<Integer>> result = new LinkedList<>();
        if(oldArrange.isEmpty()){
            List<Integer> originArray = new ArrayList<>();
            originArray.add(num);
            result.add(originArray);
            return result;
        }
        for(List<Integer> oneArray : oldArrange){
            int i=0;
            while(i<=oneArray.size()){
                List<Integer> newArray = getNewArray(oneArray, i, num);
                result.add(newArray);
                i++;
            }
        }
        return result;
    }

    private List<Integer> getNewArray(List<Integer> oldArray, int insertIndex, int num){
        int i=0;
        List<Integer> result = new ArrayList<>();
        for(;i<insertIndex;i++){
            result.add(oldArray.get(i));
        }
        result.add(num);
        for(;i<oldArray.size();i++){
            result.add(oldArray.get(i));
        }
        return result;
    }



    public void test() {
        int[] nums = {2};
        List<List<Integer>> result = permute(nums);
        return;
    }
}
